Mining the Web 2.0 for Better Search.

Fast Intersection Algorithms for Sorted Sequences.
Abstract. This work presents an experimental comparison of intersection algorithms for sorted sequences, including the recent algorithm of Baeza-Yates. This algorithm performs on average less comparisons than the total number of elements of both inputs (n and m respectively) when n = αm (α&gt; 1). We can find applications of this algorithm on query processing in Web search engines, where large intersections, or differences, must be performed fast. In this work we concentrate in studying the behavior of the algorithm in practice, using for the experiments test data that is close to the actual conditions of its applications. We compare the efficiency of the algorithm with other intersection algorithm and we study different optimizations, showing that the algorithm is more efficient than the alternatives in most cases, especially when one of the sequences is much larger than the other. 1
Towards a Distributed Search Engine.

Web search solved%3F all result rankings the same%3F

Retrieval Evaluation in Practice.

Web Advertising.
Advertising is an important source of income for many websites. To get the attention of the unsuspecting (and probably uninterested) visitors, web advertisements (ads) tend to use elaborate animations and graphics. Depending on the specific technology being used, displaying such ads on the visitor&#039;s screen may require a vast amount of CPU-power. Since present day desktop-CPUs can easily use 100W or more, ads may consume a substantial amount of energy. Although it is important for environmental reasons to reduce energy consumption, increasing the number of ads seems to be counterproductive. The goal of this paper is to investigate the power consumption of web advertisements. For this purpose we used an energy meter to measure the differences in PC power consumption while browsing the web normally (thus with ads enabled), and while browsing with ads being blocked. To simulate normal web browsing, we created a browser-based tool called AutoBrowse, which periodically opens an URL from a predefined list. To block advertisements, we used the Adblock Plus extension for Mozilla Firefox. To measure also power consumption with other browsers, we used in addition the Apache HTTP server and its mod_proxy module to act as an adblocking proxy server. The measurements on several PCs and browsers show that, on average, the additional energy consumption to display web advertisements is 2.5W. To put this number into perspective, we calculated that the total amount of energy used to display web advertisement is equivalent of the total yearly electricity consumption of nearly 2000 households in the Netherlands. It takes 3,6 “average ” wind turbines to generate this amount of energy.
Coniunge et Impera Multiple%2DGraph Mining for Query%2DLog Analysis.

Coniunge et Impera Multiple%2DGraph Mining for Query%2DLog Analysis.


Searching the Web of Objects.
As the web evolves, increasing quantities of structured information is embedded in web pages in disparate formats. For example, a digital camera’s description may include its price and megapixels whereas a professor’s description may include her name, university, and research interests. Both types of pages may include additional ambiguous information. General search engines (GSEs) do not support queries over these types of data because they ignore the web document semantics. Conversely, describing requisite semantics through structured queries into databases populated by information extraction (IE) techniques are expensive and not easily adaptable to new domains. This paper describes a methodology for rapidly developing search engines capable of answering structured queries over unstructured corpora by utilizing machine learning to avoid explicit IE. We empirically show that with minimum additional human effort, our system outperforms a GSE with respect to structured queries with clear object semantics.

Query forwarding in geographically distributed search engines.

Web retrieval the role of users.

Mining Large Query Induced Graphs towards a Hierarchical Query Folksonomy.

Temporal Analysis of Document Collections Framework and Applications.

A Model for Automatic Generation of Multi%2Dpartite Graphs from Arbitrary Data.

Tuning the capacity of search engines Load%2Ddriven routing and incremental caching to reduce and balance the load.

Capacity Planning for Vertical Search Engines

Visual Web Mining for Website Evaluation.

WCL2R A Benchmark Collection for Learning to Rank Research with Clickthrough Data.

Sync%2FAsync parallel search for the efficient design and construction of web search engines.

Privacy%2Dpreserving query log mining for business confidentiality protection.

Proceedings of the Second International Conference on Web Search and Web Data Mining

Weaving Services and People on the World Wide Web

Towards a Distributed Search Engine.

On the feasibility of multi%2Dsite web search engines.

Clustering and exploring search results using timeline constructions.

Media on the web
Abstract: Problem statement: As distributed real-time multimedia services are accessed by users from different locations, the run-time performance must be managed and monitored to get a clear view of how media web services perform within their operational environments and to perform control actions to modify and adjust the their behavior. Otherwise it will provide negative effects on the reputation of service provider. Therefore the main objective of this study was to design and implement a media web service composed dynamically and to monitor the Dynamically Composed Media Web Services (DCMWS) through Parallel Performance Monitoring Service (PPMS). The PPMS is a web service that executed in parallel with media web service using multi threading technology. Approach: The PPMS monitors the run-time performance of Dynamically Composed Media Web Services (DCMWS) which were represented as BPEL (Business Process Execution Language) processes. The run-time performance of the media web services such as timeouts, external errors, percentage of successful completion of individual media web services and the occurrence of fault were monitored and using this result the corrective actions were taken by service providers. Results: The effectiveness of PPMS had been evaluated for media-on-demand composite web service and its results showed an improvement on the performance of run time monitoring of media web services. Conclusion: To facilitate management decisions and media web service behavior modifications, service providers need to monitor the runtime performance of DCMWS. In this context, the approach outlined in this study was most appropriate, convenient and efficient. The proposed PPMS herein played a crucial role in monitoring run-time performance of DCMWS. Key words: Dynamic service composition, media-on-demand, multi threading, PPMS
A Study of the Impact of Index Updates on Distributed Query Processing for Web Search.

Relating content through web usage.

New Techniques for Visualising Web Navigational Data.

Keynote Talk Mining the Web 2.0 for Improved Image Search %28the talk was given by Roelof van Zwol

Towards a Distributed Search Engine.

Towards a Distributed Search Engine.

Efficiency trade%2Doffs in two%2Dtier web search systems.

Efficiency trade%2Doffs in two%2Dtier web search systems.



Two%2DDimensional Distributed Inverted Files.
Abstract. Term-partitioned indexes are generally inefficient for the evaluation of conjunctive queries, as they require the communication of long posting lists. On the other side, document-partitioned indexes incur in excessive overheads as the evaluation of every query involves the participation of all the processors, therefore their scalability is not adequate for real systems. We propose to arrange a set of processors in a two-dimensional array, applying term-partitioning at row level and document-partitioning at column level. Choosing the adequate number of rows and columns given the available number of processors, together with the selection of the proper ways of partitioning the index over that topology is the subject of this paper. 1
Next Generation Web Search.
The current state of web search is most successful at directing users to appropriate web sites. Once at the site, the user has a choice of following hyperlinks or using site search, but the latter is notoriously problematic. One solution is to develop specialized search interfaces that explicitly support the types of tasks users perform using the information specific to the site. A new way to support task-based site search is to dynamically present appropriate metadata that organizes the search results and suggests what to look at next, as a personalized intermixing of search and hypertext.  
User generated content how good is it%3F

A model for fast web mining prototyping.

Structured Document Retrieval.
Focussed structured document retrieval aims at retrieving best entry  points from where users can browse to access relevant document components in  the document structure. In this paper, we report on the development, implementation  and evaluation of best entry point retrieval strategies derived from  user studies designed to elicit what constitutes a best entry point.
The Geographical Life of Search.
This article describes a geographical study on the usage of a search engine, focusing on the traffic details at the level of countries and continents. The main objective is to understand from a geographic point of view, how the needs of the users are satisfied, taking into account the geographic location of the host in which the search originates, and the host that contains the Web page that was selected by the user in the answers. Our results confirm that the Web is a cultural mirror of society and shed light on the implicit social network behind search. These results are also useful as input for the design of distributed search engines. 1.
Structured Document Retrieval.
Focussed structured document retrieval aims at retrieving best entry  points from where users can browse to access relevant document components in  the document structure. In this paper, we report on the development, implementation  and evaluation of best entry point retrieval strategies derived from  user studies designed to elicit what constitutes a best entry point.
Structured Text Retrieval Models.

The Components and Impact of Sponsored Search.

Information systems special issue on ACM CIKM 2007.

On the size of Boyer%2DMoore automata.
. We study the size of Boyer-Moore automata introduced in Knuth, Morris &amp; Pratt&#039;s famous paper on pattern matching. We experimentally exhibit a finite class of binary patterns, which produce large Boyer-Moore automata. The best approximation curve for their sizes is a polynomial O(m  7  ), or even an exponential O(2  0:4m  ), in the length m  of the patterns. All the previously known maximal sizes were at most cubic in m. Our results suggest to study two particular infinite classes of patterns, for which we conjecture that the generated automata have size\Omega\Gamma  m  5  ). 1 Introduction  The string matching problem appears in many applications in computer science, like word processing, text editing, data retrieval, symbol manipulation, etc. This problem has been extensively studied in theoretical computer science [2, 11], since the two historical papers by Knuth, Morris &amp; Pratt [18], and by Boyer &amp; Moore [6], both published in 1977. The string matching problem consists in finding ...
Proceedings of the Latin American Web Conference

Web Mining or The Wisdom of the Crowds.

Improved query difficulty prediction for the web.

Data challenges at Yahoo%21

From Capturing Semantics to Semantic Search A Virtuous Cycle.

Towards A Distributed Search Engine.

Human or Automatic Answers%3F A User%27s Based Study.

Evolution of the Chilean Web A Larger Study.

A Web Search Analysis Considering the Intention behind Queries.

Towards Semantic Search.
Todays web search engines try to offer services for finding various information in addition to simple web pages, like showing locations or answering simple fact queries. Understanding the association of named entities and documents is one of the key steps towards such semantic search tasks. This paper addresses the ranking of entities and models it in a graph-based relevance propagation framework. In particular we study the problem of expert finding as an example of an entity ranking task. Entity containment graphs are introduced that represent the relationship between text fragments on the one hand and their contained entities on the other hand. The paper shows how these graphs can be used to propagate relevance information from the pre-ranked text fragments to their entities. We use this propagation framework to model existing approaches to expert finding based on the entity’s indegree and extend them by recursive relevance propagation based on a probabilistic random walk over the entity containment graphs. Experiments on the TREC expert search task compare the retrieval performance of the different graph and propagation models. 1.
ResIn a combination of results caching and index pruning for high%2Dperformance web search engines.
Results caching is an efficient technique for reducing the query processing load, hence it is commonly used in real search engines. This technique, however, bounds the maximum hit rate due to the large fraction of singleton queries, which is an important limitation. In this paper we propose ResIn- an architecture that uses a combination of results caching and index pruning to overcome this limitation. We argue that results caching is an inexpensive and efficient way to reduce the query processing load and show that it is cheaper to implement compared to a pruned index. At the same time, we show that index pruning performance is fundamentally affected by the changes in the query traffic that the results cache induces. We experiment with real query logs and a large document collection, and show that the combination of both techniques enables efficient reduction of the query processing costs and thus is practical to use in Web search engines.
ResIn a combination of results caching and index pruning for high%2Dperformance web search engines.
Results caching is an efficient technique for reducing the query processing load, hence it is commonly used in real search engines. This technique, however, bounds the maximum hit rate due to the large fraction of singleton queries, which is an important limitation. In this paper we propose ResIn- an architecture that uses a combination of results caching and index pruning to overcome this limitation. We argue that results caching is an inexpensive and efficient way to reduce the query processing load and show that it is cheaper to implement compared to a pruned index. At the same time, we show that index pruning performance is fundamentally affected by the changes in the query traffic that the results cache induces. We experiment with real query logs and a large document collection, and show that the combination of both techniques enables efficient reduction of the query processing costs and thus is practical to use in Web search engines.
Clique Analysis of Query Log Graphs.

Genealogical trees on the web a search engine user perspective.

Query%2Dsets using implicit feedback and query patterns to organize web documents.
Search System
Deterministic Searching on the Line.

Near%2DTerm Prospects for Semantic Technologies.

Web retrieval Techniques for the aggregation and selection of queries and answers.


Link analysis for Web spam detection.
We propose link-based techniques for automating the detection of Web spam, a term referring to pages which use deceptive techniques to obtain undeservedly high scores in search engines. The issue of Web spam is widespread and difficult to solve, mostly due to the large size of the Web which means that, in practice, many algorithms are infeasible. We perform a statistical analysis of a large collection of Web pages. In particular, we compute statistics of the links in the vicinity of every Web page applying rank propagation and probabilistic counting over the entire Web graph in a scalable way. We build several automatic web spam classifiers using different techniques. This paper presents a study of the performance of each of these classifiers alone, as well as their combined performance. Based on these results we propose spam detection techniques which only consider the link structure of Web, regardless of page contents. These statistical features are used to build a classifier that is tested over a large collection of Web link spam. After ten-fold cross-validation, our best classifiers have a performance comparable to that of state-of-the-art spam classifiers that use content attributes, and orthogonal to their methods.
Design trade%2Doffs for search engine caching.


Fifth Latin American Web Congress %28LA%2DWeb 2007%29

String Processing and Information Retrieval
Abstract. Given a sequence S = s1s2... sn of integers smaller than r = O(polylog(n)), we show how S can be represented using nH0(S) + o(n) bits, so that we can know any sq, as well as answer rank and select queries on S, in constant time. H0(S) is the zero-order empirical entropy of S and nH0(S) provides an Information Theoretic lower bound to the bit storage of any sequence S via a fixed encoding of its symbols. This extends previous results on binary sequences, and improves previous results on general sequences where those queries are answered in O(log r) time. For larger r, we can still represent S in nH0(S) + o(n log r) bits and answer queries in O(log r / log log n) time. Another contribution of this paper is to show how to combine our compressed representation of integer sequences with an existing compression boosting technique to design compressed full-text indexes that scale well with the size of the input alphabet Σ. Namely, we design a variant of the FM-index that indexes a string T [1, n] within nHk(T) + o(n) bits of storage, where Hk(T) is the k-th order empirical entropy of T. This space bound holds simultaneously for all k ≤ α log |Σ | n, constant 0 &lt; α &lt; 1, and |Σ |  = O(polylog(n)). This index counts the occurrences of an arbitrary pattern P [1, p] as a substring of T in O(p) time; it locates each pattern occurrence in O(log 1+ε n) time, for any constant 0 &lt; ε &lt; 1; and it reports a text substring of length ℓ in O(ℓ + log 1+ε n) time.
Mining Queries.
Levelwise algorithms (e.g., the Apriori algorithm) have been proved effective for association rule mining from sparse data. However, in many practical applications, the computation turns to be intractable for the user-given frequency threshold and the lack of focus leads to huge collections of frequent itemsets. To tackle these problems, two promising issues have been investigated during the last four years: the efficient use of user defined constraints and the computation of condensed representations for frequent itemsets, e.g., the frequent closed sets. We show that the benefits of these two approaches can be combined into a levelwise algorithm. It can be used for the discovery of association rules in difficult cases (dense and highly correlated data). For instance, we report an experimental validation related to the discovery of association rules with negations.
Challenges on Distributed Web Retrieval.
In the ocean of Web data, Web search engines are the primary way to access content. As the data is on the order of petabytes, current search engines are very large centralized systems based on replicated clusters. Web data, however, is always evolving. The number of Web sites continues to grow rapidly and there are currently more than 20 billion indexed pages. In the near future, centralized systems are likely to become ineffective against such a load, thus suggesting the need of fully distributed search engines. Such engines need to achieve the following goals: high quality answers, fast response time, high query throughput, and scalability. In this paper we survey and organize recent research results, outlining the main challenges of designing a distributed Web retrieval system.
Load%2Dbalancing and caching for collection selection architectures.
Abstract — To address the rapid growth of the Internet, modern Web search engines have to adopt distributed organizations, where the collection of indexed documents is partitioned among several servers, and query answering is performed as a parallel and distributed task. Collection selection can be a way to reduce the overall computing load, by finding a trade-off between the quality of results retrieved and the cost of solving queries. In this paper, we analyze the relationship between the collection selection strategy, the effect on load balancing and on the caching subsystem, by exploring the design-space of a distributed search engine based on collection selection. In particular, we propose a strategy to perform collection selection in a load-driven way, and a novel caching policy able to incrementally refine the effectiveness of the results returned for each subsequent cache hit. The combination of load-driven collection selection and incremental caching strategies allows our system to retrieve two thirds of the top-ranked results returned by a baseline centralized index, with only one fifth of the computing workload. I.
Extracting semantic relations from query logs.

Distinctive Features of the Argentinian Web.

New Stochastic Algorithms for Scheduling Ads in Sponsored Search.

Website Privacy Preservation for Query Log Publishing.%
In this paper we study privacy preservation for the publication of search engine query logs. In particular, we introduce a new privacy concern, which is that of website privacy (or business privacy). We define the possible adversaries that could be interested in disclosing website information and the vulnerabilities found in the query log, from which they could benefit. In this work we also detail anonymization techniques to protect website information, and explore the different types of attacks that an adversary could use. We then present a graph-based heuristic to validate the effectiveness of our anonymization method, and perform an experimental evaluation of this approach. Our experimental results show that the query log can be appropriately anonymized against a specific attack for website exposure, by only removing approximately 9 % of the total volume of queries and clicked URLs.
Website Privacy Preservation for Query Log Publishing.%
In this paper we study privacy preservation for the publication of search engine query logs. In particular, we introduce a new privacy concern, which is that of website privacy (or business privacy). We define the possible adversaries that could be interested in disclosing website information and the vulnerabilities found in the query log, from which they could benefit. In this work we also detail anonymization techniques to protect website information, and explore the different types of attacks that an adversary could use. We then present a graph-based heuristic to validate the effectiveness of our anonymization method, and perform an experimental evaluation of this approach. Our experimental results show that the query log can be appropriately anonymized against a specific attack for website exposure, by only removing approximately 9 % of the total volume of queries and clicked URLs.
Search results using timeline visualizations.
As search applications keep gathering new and diverse information sources, presenting relevant information anchored in time becomes more important. Time can help in describing the context of a document or document collection or in recreating a particular historical period. Temporal information is available in every document either explicitly or implicitly. Recognizing such temporal information and exploiting it for document retrieval and presentation purposes are important features that can significantly improve the functionality of today’s search applications. A look at functionality of any of the current search engines shows that temporal aspects of documents are exclusively used to sort the hit list by date, which is primarily the date a Web page or a document has been created or last modified. In this demonstration, we present a new approach in which search results are arranged in a well-defined timeline using a few existing visualization metaphors.
The impact of caching on search engines.

Search results using timeline visualizations.
As search applications keep gathering new and diverse information sources, presenting relevant information anchored in time becomes more important. Time can help in describing the context of a document or document collection or in recreating a particular historical period. Temporal information is available in every document either explicitly or implicitly. Recognizing such temporal information and exploiting it for document retrieval and presentation purposes are important features that can significantly improve the functionality of today’s search applications. A look at functionality of any of the current search engines shows that temporal aspects of documents are exclusively used to sort the hit list by date, which is primarily the date a Web page or a document has been created or last modified. In this demonstration, we present a new approach in which search results are arranged in a well-defined timeline using a few existing visualization metaphors.
Graphs from Search Engine Queries.
Abstract. Finding sparse cuts is an important tool for analyzing large graphs that arise in practice, such as the web graph, online social communities, and VLSI circuits. When dealing with such graphs having billions of nodes, it is often hard to visualize global partitions. While studies on sparse cuts have traditionally looked at cuts with respect to all the nodes in the graph, some recent works analyze graph properties projected onto a small subset of vertices that may be of interest in a given context, e.g., relevant documents to a query in a search engine. In this paper, we study how sparse cuts in a graph partition a certain subset of nodes. We call this partition a cut projection. We study the problem of finding cut projections in the streaming model that is appropriate in this context as the input graph is too large to store in main memory. Specifically, for a d-regular graph G on n nodes with a cut of conductance Φ and constant balance, we show how to parti-1 tion a randomly chosen set of k nodes in Õ( αΦ) passes over the graph stream and space Õ(nα + n3/4 k 1/4 αΦ 19/4), for any choice of α ≤ 1. The resulting partition is the projection of a cut of conductance of at most Õ(√Φ). We note that for k &lt; nα 6 Φ O(1) , this can be done in Õ(1/√αΦ) passes and space Õ(nα) that is sublinear in the number of nodes. 1
Admission Policies for Caches of Search Engine Results.
Abstract. This paper studies the impact of the tail of the query distribution on caches of Web search engines, and proposes a technique for achieving higher hit ratios compared to traditional heuristics such as LRU. The main problem we solve is the one of identifying infrequent queries, which cause a reduction on hit ratio because caching them often does not lead to hits. To mitigate this problem, we introduce a cache management policy that employs an admission policy to prevent infrequent queries from taking space of more frequent queries in the cache. The admission policy uses either stateless features, which depend only on the query, or stateful features based on usage information. The proposed management policy is more general than existing policies for caching of search engine results, and it is fully dynamic. The evaluation results on two different query logs show that our policy achieves higher hit ratios when compared to previously proposed cache management policies. 1
XML retrieval db%2Fir in theory%2C web in practice.

Characterization of national Web domains.
During the last few years, several studies on the characterization of the public Web space of various national domains have been published. The pages of a country are an interesting set for studying the characteristics of the Web, because at the same time these are diverse (as they are written by several authors) and yet rather similar (as they share a common geographical, historical and cultural context). This paper discusses the methodologies used for presenting the results of Web characterization studies, including the granularity at which different aspects are presented, and a separation of concerns between contents, links, and technologies. Based on this, we present a side-by-side comparison of the results of 12 Web characterization studies comprising over 120 million pages from 24 countries. The comparison unveils similarities and differences between the collections, and sheds light on how certain results of a single Web characterization study on a sample may be valid in the context of the full Web.
Analyzing imbalance among homogeneous index servers in a web search system.

A pipelined architecture for distributed text query evaluation.

Generic Damping Functions for Propagating Importance in Link%2DBased Ranking.
Generic damping functions for propagating importance in link-based ranking. (English summary) Internet Math. 3 (2006), no. 4, 445–478. Summary: “This paper introduces a family of link-based ranking algorithms that propagate page importance through links. The algorithms include a damping function that decreases with distance, thus a direct link implies greater endorsement than a link via a longer path. PageRank is the most widely known ranking function of this family. “The main objective of this paper is to determine whether this family of ranking techniques is of some interest per se and how different choices for the damping function affect rank quality and convergence speed. Even though our results suggest that PageRank can be approximated with other, more simple forms of rankings that may be computed more efficiently, our focus is more speculative in nature, given that it aims at separating the kernel of PageRank, that is, link-based importance propagation, from the way propagation decays over paths. “We focus on three damping functions that have, respectively, linear, exponential, and hyperbolic decay on the lengths of the paths. The exponential decay corresponds to PageRank, and the
2004 Symposium on String Processing and Information Retrieval.

Crawling the Infinite Web.
A large amount of the publicly available Web pages is generated dynamically upon request,  and contain links to other dynamically generated pages. Many Web sites that are built with dynamic  pages can create arbitrarily many pages. This poses a problem for the crawlers of Web search engines, as  the network and storage resources required for indexing Web pages are neither infinite nor free. In this  article, several probabilistic models for user browsing in &#034;infinite&#034; Web sites are proposed and studied.
Improving search engines by query clustering.


On the value of temporal information in information retrieval.


Link%2DBased Characterization and Detection of Web Spam.
We perform a statistical analysis of a large collection of Web pages, focusing on spam detection. We study several metrics such as degree correlations, number of neighbors, rank propagation through links, TrustRank and others to build several automatic web spam classifiers. This paper presents a study of the performance of each of these classifiers alone, as well as their combined performance. Using this approach we are able to detect 80.4% of the Web spam in our sample, with only 1.1% of false positives.
Modeling performance%2Ddriven workload characterization of web search systems.
Search and Retrieval]:Search process
Text Mining of Business News for Forecasting.

Where and How Duplicates Occur in the Web.

Analysis of Web Search Engine Clicked Documents.

Algorithmic Challenges in Web Search Engines.
We propose a general framework for learning from labeled and unlabeled data on a directed graph in which the structure of the graph including the directionality of the edges is considered. The time complexity of the algorithm derived from this framework is nearly linear due to recently developed numerical techniques. In the absence of labeled instances, this framework can be utilized as a spectral clustering method for directed graphs, which generalizes the spectral clustering approach for undirected graphs. We have applied our framework to real-world web classification problems and obtained encouraging results. 1.
Generalizing PageRank damping functions for link%2Dbased ranking algorithms.
This paper introduces a family of link-based ranking algorithms that propagate page importance through links. In these algorithms there is a damping function that decreases with distance, so a direct link implies more endorsement than a link through a long path. PageRank is the most widely known ranking function of this family. The main objective of this paper is to determine whether this family of ranking techniques has some interest per se, and how different choices for the damping function impact on rank quality and on convergence speed. Even though our results suggest that Page-Rank can be approximated with other simpler forms of rankings that may be computed more efficiently, our focus is of more speculative nature, in that it aims at separating the kernel of PageRank, that is, link-based importance propagation, from the way propagation decays over paths. We focus on three damping functions, having linear, exponential, and hyperbolic decay on the lengths of the paths. The exponential decay corresponds to PageRank, and the other functions are new. Our presentation includes algorithms, analysis, comparisons and experiments that study their behavior under different parameters in real Web graph data. Among other results, we show how to calculate a linear approximation that induces a page ordering that is almost identical to Page-Rank’s using a fixed small number of iterations; comparisons were performed using Kendall’s τ on large domain datasets.
The Intention Behind Web Queries.
Web search engines typically provide search results without considering user interests or context. We propose a personalized search approach that can easily extend a conventional search engine on the client side. Our mapping framework automatically maps a set of known user interests onto a group of categories in the Open Directory Project (ODP) and takes advantage of manually edited data available in ODP for training text classifiers that correspond to, and therefore categorize and personalize search results according to user interests. In two sets of controlled experiments, we compare our personalized categorization system (PCAT) with a list interface system (LIST) that mimics a typical search engine and with a nonpersonalized categorization system (CAT). In both experiments, we analyze system performances on the basis of the type of task and query length. We find that PCAT is preferable to LIST for information gathering types of tasks and for searches with short queries, and PCAT outperforms CAT in both information gathering and finding types of tasks, and for searches associated with free-form queries. From the subjects ’ answers to a questionnaire, we find that PCAT is perceived as a system that can find relevant Web pages quicker and easier
Relationship between web links and trade.
We report on observations on Web characterization studies that suggest that the amount of Web links among sites under di#erent country-code top-level domains is related to the amount of trade between the corresponding countries.
Algorithmic Challenges in Web Search Engines.
We propose a general framework for learning from labeled and unlabeled data on a directed graph in which the structure of the graph including the directionality of the edges is considered. The time complexity of the algorithm derived from this framework is nearly linear due to recently developed numerical techniques. In the absence of labeled instances, this framework can be utilized as a spectral clustering method for directed graphs, which generalizes the spectral clustering approach for undirected graphs. We have applied our framework to real-world web classification problems and obtained encouraging results. 1.
Analysis of Web Search Engine Query Session and Clicked Documents.

Understanding Content Reuse on the Web Static and Dynamic Analyses.
Abstract. In this paper we present static and dynamic studies of duplicate and near-duplicate documents in the Web. The static and dynamic studies involve the analysis of similar content among pages within a given snapshot of the Web and how pages in an old snapshot are reused to compose new documents in a more recent snapshot. We ran a series of experiments using four snapshots of the Chilean Web. In the static study, we identify duplicates in both parts of the Web graph – reachable (connected by links) and unreachable components (unconnected)  – aiming to identify where duplicates occur more frequently. We show that the number of duplicates in the Web seems to be much higher than previously reported (about 50 % higher) and in our data the duplicated in the unreachable Web is 74,6 % higher than the number of duplicates in the reachable component of the Web graph. In the dynamic study, we show that some of the old content is used to compose new pages. If a page in a newer snapshot has content of a page in an older snapshot, we say that the source is a parent of the new page. We state the hypothesis that people use search engines to find pages and republish their content as a new document. We present evidences that this happens for part of the pages that have parents. In this case, part of the Web content is biased by the ranking function of search engines. 1
Relationship between web links and trade.
We report on observations on Web characterization studies that suggest that the amount of Web links among sites under di#erent country-code top-level domains is related to the amount of trade between the corresponding countries.
A content and structure website mining model.

Introduction to the special issue on XML retrieval.

Dynamics of the Chilean Web structure.

Advances in information retrieval An introduction to the special issue.

SIGIR 2005 Proceedings of the 28th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval

Pagerank Increase under Different Collusion Topologies.

Database and Information Retrieval Techniques for XML.

Applications of a Web Information Mining Model to Data Mining and Information Retrieval Tasks.

WIM An Information Mining Model for the Web.

A Case Study News Classification Based on Term Frequency.

Applications of Web Query Mining.
Abstract. Server logs of search engines store traces of queries submitted by users, which include queries themselves along with Web pages selected in their answers. The same is true in Web site logs where queries and later actions are recorded from search engine referrers or from an internal search box. In this paper we present two applications based in analyzing and clustering queries. The first one suggest changes to improve the text and structure of a Web site and the second does relevance ranking boosting and query recommendation in search engines. 1
A Website Mining Model Centered on User Queries.
Abstract. We present a model for mining user queries found within the access logs of a website and for relating this information to the website’s overall usage, structure and content. The aim of this model is to discover, in a simple way, valuable information to improve the quality of the website, allowing the website to become more intuitive and adequate for the needs of its users. This model presents a methodology of analysis and classification of the different types of queries registered in the usage logs of a website, such as queries submitted by users to the site’s internal search engine and queries on global search engines that lead to documents in the website. These queries provide useful information about topics that interest users visiting the website and the navigation patterns associated to these queries indicate whether or not the documents in the site satisfied the user’s needs at that moment. 1
WIM An Information Mining Model for the Web.

Modeling User Search Behavior.
Web usage mining is a main research area in Web mining focused on learning about Web users and their interactions with Web sites. Main challenges in Web usage mining are the application of data mining techniques to Web data in an efficient way and the discovery of non trivial user behaviour patterns. In this paper we focus the attention on search engines analyzing query log data and showing several models about how users search and how users use search engine results. 1.
Characterizing Objectionable Image Content %28Pornography and Nude Images%29 of Specific Web Segments Chile as a Case Study.

Web Mining.

Experimental Analysis of a Fast Intersection Algorithm for Sorted Sequences.
Abstract. This work presents an experimental comparison of intersection algorithms for sorted sequences, including the recent algorithm of Baeza-Yates. This algorithm performs on average less comparisons than the total number of elements of both inputs (n and m respectively) when n = αm (α&gt; 1). We can find applications of this algorithm on query processing in Web search engines, where large intersections, or differences, must be performed fast. In this work we concentrate in studying the behavior of the algorithm in practice, using for the experiments test data that is close to the actual conditions of its applications. We compare the efficiency of the algorithm with other intersection algorithm and we study different optimizations, showing that the algorithm is more efficient than the alternatives in most cases, especially when one of the sequences is much larger than the other. 1
Crawling a country better strategies than breadth%2Dfirst for web page ordering.
This article compares several page ordering strategies for Web crawling under several metrics. The objective of these strategies is to download the most ``important&#039;&#039; pages ``early&#039;&#039; during the crawl. As the coverage of modern search engines is small compared to the size of the Web, and it is impossible to index all of the Web for both theoretical and practical reasons, it is relevant to index at least the most important pages. We use data from actual Web pages to build Web graphs and execute a crawler simulator on those graphs. As the Web is very dynamic, crawling simulation is the only way to ensure that all the strategies considered are compared under the same conditions. We propose several page ordering strategies that are more efficient than breadth-first search and strategies based on partial Pagerank calculations.
Foreword.
reference set of international guidelines and recommendations for the reporting and presentation of statistical data and metadata. Although, the Handbook was prepared primarily for short-term economic statistics, many, if not most of the recommendations presented are also relevant for annual (structural) statistics and for social and population statistics. The Handbook draws heavily on existing international statistical guidelines and recommendations that have been developed over the last twenty years by international organisations and national statistical agencies. These international standards have been developed for implementation by international organisations themselves and by national agencies in both developed and developing economies. The need for the articulation of a comprehensive set of recommendations on the reporting and presentation of statistical data and metadata is one aspect of the overall demand for improved international comparability and consistency of statistics compiled and published by national agencies and international organisations. This requirement has itself been driven by closer economic and social linkages between both the 30 OECD Member countries and between those countries and large emerging non-member economies. As discussed in the Handbook, the major causes of differences in statistics compiled in different countries flow from the use of different definitions and concepts and
Web Mining in Search Engines.

Query Clustering for Boosting Web Page Ranking.

Challenges in the Interaction of Information Retrieval and Natural Language Processing.

Content%2DBased Image Retrieval and Characterization on Specific Web Collections.
One of the challenges in image and video retrieval is the content-based  retrieval of images and videos in the web. Less work has been done in this area,  mainly due to scalability issues. For this reason, in this paper we investigate this  problem by presenting tools for the characterization of the visual contents on  specific web collections and a strategy for the search of faces in the web using visual  and text information. A case study is also presented in a specific web domain.
A Fast Set Intersection Algorithm for Sorted Sequences.

An Optimistic Model for Searching Web Directories.

Query Recommendation Using Query Logs in Search Engines.
Abstract. In this paper we propose a method that, given a query submitted to a search engine, suggests a list of related queries. The related queries are based in previously issued queries, and can be issued by the user to the search engine to tune or redirect the search process. The method proposed is based on a query clustering process in which groups of semantically similar queries are identified. The clustering process uses the content of historical preferences of users registered in the query log of the search engine. The method not only discovers the related queries, but also ranks them according to a relevance criterion. Finally, we show with experiments over the query log of a search engine the effectiveness of the method. 1
The Continued Saga of DB%2DIR Integration.

Semantic Search in the WWW Supported by a Cognitive Model.

Crawling the Infinite Web Five Levels Are Enough.
Abstract. A large amount of publicly available Web pages are generated dynamically upon request, and contain links to other dynamically generated pages. This usually produces Web sites which can create arbitrarily many pages. In this article, several probabilistic models for browsing “infinite ” Web sites are proposed and studied. We use these models to estimate how deep a crawler must go to download a significant portion of the Web site content that is actually visited. The proposed models are validated against real data on page views in several Web sites, showing that, in both theory and practice, a crawler needs to download just a few levels, no more than 3 to 5 “clicks ” away from the start page, to reach 90 % of the pages that users actually visit. 1
Web page ranking using link attributes.
We present a variant of PageRank, WLRank, that considers di#erent Web page attributes to give more weight to some links, improving the precision of the answers.
Scheduling Algorithms for Web Crawling.
es, enforcing a politeness policy as described in Section ??: a Web crawler should not download more than one page from a single Web site at a time, and it should wait several seconds between requests.  (a) Full parallelization (b) Full serialization  Figure 6.1: Two unrealistic scenarios for Web crawling: (a) parallelizing all page downloads and (b) serializing all page downloads. The areas represent page sizes, as size = speed  time.  Instead of downloading all pages in parallel, we could also serialize all the requests, downloading only one page at a time at the maximum speed, as depicted in Figure 6.1b. However, the bandwidth available for Web sites B  i is usually lower than the crawler bandwidth B, so this scenario is not realistic either.  The presented observations suggest that actual download time lines are similar to the one shown in Figure 6.2. In the Figure, the optimal time T    is not achieved, because some bandwidth is wasted due to limitations in the speed of Web sites 
Web Dynamics%2C Structure%2C and Page Quality.
Introduction  The purpose of a Web search engine is to provide an infrastructure that supports relationships between publishers of content and readers. In this context, as the numbers involved are very big (550 million users [2] and more than 3 billion pages (a lower bound that comes from the coverage of popular search engines) in 35 million sites [4] on January 2003) it is critical to provide good measures of quality that allow the user to choose &#034;good&#034; pages. We think that this is the main element that explain Google&#039;s [3] success. However, the notion of what is a &#034;good page&#034; and how this it is related to different Web characteristics is not well understood.  Therefore, in this chapter we address the study of the relationships between the age of a page or a site, the quality of a page, and the structure of the Web. Age is defined as the time since the page was last updated (recency). For Web servers, we use the oldest page in the site as a lower bound on the age of the site.  The spe
Editorial.
calls &amp; calendarEDITORIAL
On the Image Content of a Web Segment Chile as a Case Study.

Third edition of the %22XML and information retrieval%22 workshop first workshop on integration of IR and DB %28WIRD%29 jointly held at SIGIR%272004

Combinatorial Pattern Matching
Techniques for indexing and retrieving text documents are well understood; their use is commonplace in web-based search services. By contrast, the state of the art in content-based retrieval of musical documents - songs - is less than satisfactory. The problem arises when we wish to find a song based on a few hummed notes, or when we wish to find repetitions of a theme in a piece of music. Applications of music information retrieval (MIR) are numerous, from tune identification and musicological studies, to questions of copyright. Complex music databases require tailored MIR solutions. As more and more musical information becomes available from many sources, efficient methods for MIR need to be developed to complete the multimedia circle.
Evolution of the Chilean Web Structure Composition.
In this paper we present the evolution of the structure of the Chilean Web between 2000 and 2002. Our results show that although the Web grows as expected, also a significant part of it disappears. In addition, some components are much more stable than others. We also compare the expected life cycle of a Web site in the structure with the actual real data.
Alternative Implementation Techniques for Web Text Visualization
We present an approach for building text visualizations that avoids using plug-ins or clients based on languages like Java. Instead we propose to make the search engine application more aware of the visualization process and use the web browser standard features to do the rendering work. We demonstrate the ideas with a text visualization metaphor implementation that is part of a search engine. Information visualization techniques can help users navigate through large sets of answers as well as selecting the appropriate web page or document [4]. Some of those visualization metaphors have been around for a number of years but they are not getting
WISDNA An Information Visualization Paradigm for XML.
  With ever-increasing amounts of data in repositories, finding the information a user needs becomes increasingly challenging. When users approach an information access system they often do not have a clear understanding of how to access the precise information they need. Additionally, it is not rare that users have only a vague notion of what they are looking for, hence the need for an exploratory navigation tool beyond a static list of search results. A model used in practice is an iterative search-and-browse cycle to retrieve relevant information. The role of the user interface in understanding search results and providing relevant metadata in a compact manner is a key component of this iterative process. In this context we present WISDNA as an information visualization paradigm for XML data from web information services.  According to the Department of Commerce U.S. online retail sales topped $32 billion in 2002, a 19 percent increase over the previous year. In 2002, co
XML Retrieval.

On the Image Content of the Chilean Web.
In this paper we perform a study of the image contents of the Chilean web (.cl domain) using automatic feature extraction, content-based analysis and face detection algorithms. In an automated process we examine all .cl websites and download a large number of the images available (approx. 83,000). Then we extract several visual features (color, texture, shape, etc.) and we perform face detection using novel algorithms. Using this process we semi-automatically characterize the image content of the web in Chile in terms of the detected faces and the visual features obtained automatically. We present statistics of use to anyone concerned with the image content of the web in Chile. Our study is the first one to use content-based tools to determine the image contents of the web.
A Three Level Search Engine Index Based in Query Log Distribution.

Evolution of the Web Structure.
We propose WebRelievo, a system for visualizing and analyzing the evolution of the web structure based on a large Web archive with a series of snapshots. It visualizes the evolution with a time series of graphs, in which nodes are web pages, and edges are relationships between pages. Graphs can be clustered to show the overview of changes in graphs. WebRelievo aligns these graphs according to their time, and automatically determines their layout keeping positions of nodes synchronized over time, so that the user can keep track pages and clusters. This visualization enables us to understand when pages appeared, how their relationships have evolved, and how clusters are merged and split over time. Current implementation of WebRelievo is based on six Japanese web archives crawled from 1999 to 2003. The user can interactively browse those graphs by changing the focused page and by changing layouts of graphs. Using WebRelievo we can answer historical questions, and to investigate changes in trends on the Web. We show the feasibility of WebRelievo by applying it to tracking trends in P2P systems and search engines for mobile phones, and to investigating link spamming.

Clustering in Metric Spaces with Applications to Information Retrieval.

Information retrieval in the Web beyond current search engines.

Matchsimile a Flexible Approximate Matching Tool for Searching Proper Name.


Optimal binary search trees with costs depending on the access paths.
We describe algorithms for constructing optimal binary search trees, in which the access cost of a key depends on the k preceding keys which were reached in the path to it. This problem has applications to searching on secondary memory and robotics. Two kinds of optimal trees are considered, namely optimal worst case trees and weighted average case trees. The time and space complexities of both algorithms are O(n ) and O(n respectively. The algorithms are based on a convenient decomposition and characterizations of sequences of keys which are paths of special kinds in binary search trees. Finally, using generating functions, we present an exact analysis of the number of steps performed by the algorithms.
Foundations of Information Technology in the Era of Networking and Mobile Computing
This paper proposes Allocational Temporal Logic (AllTL) as a formalism to express properties concerning the dynamic allocation (birth) and de-allocation (death) of entities, such as the objects in an object-based system. The logic is interpreted on History-Dependent Automata, extended with a symbolic representation for certain cases of unbounded allocation. The paper also presents a simple imperative language with primitive statements for (de)allocation, with an operational semantics, to illustrate the kind of behaviour that can be modelled. The main contribution of the paper is a tableau-based model checking algorithm for along the lines of Lichtenstein and Pnueli&#039;s algorithm for LTL.
Agents%2C Crawlers%2C and Web Retrieval.

Balancing Volume%2C Quality and Freshness in Web Crawling.
We describe a crawling software designed for high-performance, large-scale information discovery and gathering on the Web. This crawler allows the administrator to seek for a balance between the volume of a Web collection and its freshness; and also provides flexibility for defining a quality metric to priorize certain pages.
Web Structure%2C Dynamics and Page Quality.
This paper is aimed at the study of quantitative measures of the relation between Web structure, page recency, and quality of Web pages. Quality is studied using different link-based metrics considering their relationship with the structure of the Web and the last modification time of a page. We show that, as expected, Pagerank is biased against new pages. As a subproduct we propose a Pagerank variant that includes page recency into account and we obtain information on how recency is related with Web structure.
Optimal bounded disorder.


Preface.
part of a series of studies in support of the California Governor’s Advisory Committee on Education Excellence. i PREFACE i LIST OF FIGURES iv
XQL and proximal nodes.
We consider the recently proposed XQL language, which is designed to query XML documents by content and structure. We show that an already existing model, namely &#034;Proximal Nodes&#034;, is the only one that addresses all the complex querying operations defined by XQL and that suggests an efficient implementation for them.
New and faster filters for multiple approximate string matching.
We present three new algorithms for on-line multiple string matching allowing errors. These  are extensions of previous algorithms that search for a single pattern. The average running  time achieved is in all cases linear in the text size for moderate error level, pattern length and number of patterns. They adapt (with higher costs) to the other cases. However, the algorithms  differ in speed and thresholds of usefulness. We analyze theoretically when each algorithm should be used, and show experimentally their performance. The only previous solution for this  problem allows only one error. Our algorithms are the first to allow more errors, and are faster  than previous work for a moderate number of patterns (e.g. less than 50-100 on English text, depending on the pattern length). 
Second edition of the %22XML and information retrieval%22 workshop held at SIGIR%272002
This part will get you started in thinking about designing and analyzing algorithms.
It is intended to be a gentle introduction to how we specify algorithms, some of the
design strategies we will use throughout this book, and many of the fundamental
ideas used in algorithm analysis. Later parts of this book will build upon this base.
Chapter 1 is an overview of algorithms and their place in modern computing
systems. This chapter defines what an algorithm is and lists some examples. It also
makes a case that algorithms are a technology, just as are fast hardware, graphical
user interfaces, object-oriented systems, and networks.
In Chapter 2, we see our first algorithms, which solve the problem of sorting
a sequence of n numbers. They are written in a pseudocode which, although not
directly translatable to any conventional programming language, conveys the structure
of the algorithm clearly enough that a competent programmer can implement
it in the language of his choice. The sorting algorithms we examine are insertion
sort, which uses an incremental approach, and merge sort, which uses a recursive
technique known as “divide and conquer.” Although the time each requires increases
with the value of n, the rate of increase differs between the two algorithms.
We determine these running times in Chapter 2, and we develop a useful notation
to express them.
Chapter 3 precisely defines this notation, which we call asymptotic notation. It
starts by defining several asymptotic notations, which we use for bounding algorithm
running times from above and/or below. The rest of Chapter 3 is primarily a
presentation of mathematical notation. Its purpose is more to ensure that your use
of notation matches that in this book than to teach you new mathematical concepts.
Flexible Comparison of Conceptual GraphsWork done under partial support of CONACyT


Distributed Query Processing Using Partitioned Inverted Files.
In this paper, we study query processing in a distributed text database. The novelty is a real distributed architecture implementation that offers concurrent query service. The distributed system adopts a network of workstations model and the client-server paradigm. The document collection is indexed with an inverted file. We adopt two distinct strategies of index partitioning in the distributed system, namely local index partitioning and global index partitioning. In both strategies, documents are ranked using the vector space model along with a document filtering technique for fast ranking. We evaluate and compare the impact of the two index partitioning strategies on query processing performance. Experimental results on retrieval efficiency show that, within our framework, the global index partitioning outperforms the local index partitioning. 1.
Relating Web Characteristics with Link Based Web Page Ranking.

Integration of Search Engines with User Interfaces.

Relating Web Structure%2C User Search Behavior.
In this paper we present some empirical results relating the Web structure and user search behavior for the Chilean (.cl) Web domain. Some of our results shed light on the correlation between Web connectivity, Web pages, and queries posed to a Chilean search engine.
Searching in metric spaces.

Improving an Algorithm for Approximate Pattern Matching.
We study a recent algorithm for fast on-line approximate string matching. This is the  problem of searching a pattern in a text allowing errors in the pattern or in the text. The  algorithm is based on a very fast kernel which is able to search short patterns using a nondeterministic  finite automaton, which is simulated using bit-parallelism. A number of techniques  to extend this kernel for longer patterns are presented in that work. However, the techniques  can be integrated in many ways and the optimal interplay among them is by no means obvious.  The solution to this problem starts at a very low level, by obtaining basic probabilistic  information about the problem which was not previously known, and ends integrating analytical  results with empirical data to obtain the optimal heuristic. The conclusions obtained via analysis  are experimentally confirmed. We also improve many of the techniques and obtain a combined  heuristic which is faster than the original work.  This work sho...
Indexing Methods for Approximate String Matching.
Indexing for approximate text searching is a novel problem receiving much attention because of its applications in signal processing, computational biology and text retrieval, to name a few. We classify most indexing methods in a taxonomy that helps understand their essential features. We show that the existing methods, rather than completely different as they are regarded, form a range of solutions whose optimum is usually somewhere in between.
Miner%EDa de texto empleando grafos conceptuales.

New Approaches to Information Management Attribute%2DCentric Data Systems %28invited paper%29.

An Image Similarity Measure Based on Graph Matching.

A Model and Software Architecture for Search Results Visualization on the WWW.

Fast and flexible word searching on compressed text.
text. When searching complex or approximate patterns, our algorithms are up to 8 times faster than the search on uncompressed text. We also discuss the impact of our technique in inverted files pointing to logical blocks and argue for the possibility of keeping the text compressed all the time, decompressing only for displaying purposes. Categories and Subject Descriptors: E.4 [Coding and Information Theory]: Data Compaction This work has been partially supported by SIAM Project, grant MCT/FINEP/PRONEX 76.97.1016.00, AMYRI/CYTED Project, CAPES scholarship (E. S. de Moura), Fondecyt grant 1990627 (G. Navarro and R. Baeza-Yates) and CNPq grant 520916/94-8 (N. Ziviani).  Authors&#039; addresses: E. S. de Moura and N. Ziviani, Dept. of Computer Science, Univ. Federal de Minas Gerais, Av. Antonio Carlos 6627, Belo Horizonte, Brazil; G. Navarro and R. Baeza-Yates, Dept. of Computer Science, Univ. de Chile, Av. Blanco Encalada 2120, Santiago, Chile.  Permission to make digital or h
Binary Searching with Nonuniform Costs and Its Application to Text Retrieval.

Compression A Key for Next%2DGeneration Text Retrieval Systems.
In this article we discuss recent methods for compressing the text and the index of text retrieval systems. By compressing both the complete text and the index, the total amount of space is less than half the size of the original text alone. Most surprisingly, the time required to build the index and also to answer a query is much less than if the index and text had not been compressed. This is one of the few cases where there is no space-time trade-off. Moreover, the text can be kept compressed all the time, allowing updates when changes occur in the compressed text.
Adding Compression to Block Addressing Inverted Indexes.
. Inverted index compression, block addressing and sequential search on compressed text are three techniques that have been separately developed for efficient, low-overhead text retrieval. Modern text compression techniques can reduce the text to less than 30% of its size and allow searching it directly and faster than the uncompressed text. Inverted index compression obtains significant reduction of their original size at the same processing speed. Block addressing makes the inverted lists point to text blocks instead of exact positions and pay the reduction in space with some sequential text scanning.  In this work we combine the three ideas in a single scheme. We present a compressed inverted file that indexes compressed text and uses block addressing. We consider different techniques to compress the index and study their performance with respect to the block size. We compare the index against three separate techniques for varying block sizes, showing that our index is superior to each isolated approach. For instance, with just 4% of extra space overhead the index has to scan less than 12% of the text for exact searches and about 20% allowing one error in the matches. Keywords: Text compression, inverted files, block addressing, text databases.  1. 
Block addressing indices for approximate text retrieval.
Although the issue of approximate text retrieval is gaining importance in the last years, it is currently addressed by only a few indexing schemes. To reduce space requirements, the indices may point to text blocks instead of exact word positions. This is called &#034;block addressing&#034;. The most notorious index of this kind is Glimpse. However, block addressing has not been well studied yet, especially regarding approximate searching. Our main contribution is an analytical study of the spacetime trade-offs related to the block size. We find that, under reasonable assumptions, it is possible to build an index which is simultaneously sublinear in space overhead and in query time. We validate the analysis with extensive experiments, obtaining typical performance figures. These results are valid not only for approximate searching queries but also for classical ones. Finally, we propose a new strategy for approximate searching on block addressing indices, which we experimentally find 4-5 times f...
Dise%F1emos Todo de Nuevo Reflexiones sobre la Computaci%F3n y su Ense%F1anza %28Invited paper%29.

Modern Information Retrieval

A New Indexing Method for Approximate String Matching.
. We present a new indexing method for the approximate string matching problem. The method is based on a suffix tree combined with a partitioning of the pattern. We analyze the resulting algorithm and show that the retrieval time is O(n    ), for 0 ! ! 1, whenever  ff ! 1 \Gamma e=  p  oe, where ff is the error level tolerated and oe is the alphabet size. We experimentally show that this index outperforms by far all other algorithms for indexed approximate searching, also being the first experiments that compare the different existing schemes. We finally show how this index can be implemented using much less space. 1 Introduction  Approximate string matching is a recurrent problem in many branches of computer science, with applications to text searching, computational biology, pattern recognition, signal processing, etc. The problem is: given a long text of length n, and a (comparatively short) pattern of length m, retrieve all the text segments (or &#034;occurrences&#034;) whose edit distance t...
Fast Multi%2Ddimensional Approximate Pattern Matching.
. We address the problem of approximate string matching in  d dimensions, that is, to find a pattern of size m  d  in a text of size n  d  with at most k ! m  d  errors (substitutions, insertions and deletions along any dimension). We use a novel and very flexible error model, for which there exists only an algorithm to evaluate the similarity between two elements in two dimensions at O(m  4  ) time. We extend the algorithm to d dimensions, at O(d!m  2d  ) time and O(d!m  2d\Gamma1  ) space. We also give the first search algorithm for such model, which is O(d!m  d  n  d  ) time and O(d!m  d  n  d\Gamma1  ) space. We show how to reduce the space cost to O(d!3  d  m  2d\Gamma1  ) with little time penalty. Finally, we present the first sublinear-time (on average) searching algorithm (i.e. not all text cells are inspected), which is O(kn  d  =m  d\Gamma1  ) for k ! (m=(d(log oe m \Gamma log oe d)))  d\Gamma1  , where oe is the alphabet size. After that error level the filter still remains ...
A Fast Algorithm on Average for All%2DAgainst%2DAll Sequence Matching.
Information is the main value of Information Society. The recent developments in computing power and telecommunications, along with the constant drop of Internet access costs and data management and storing, created the right conditions for the global diffusion of the Web and, more generally, of new research tools able to analyze information and their contents. Depending on the particular application scenario and on the type of information that has to be managed and searched, different techniques need to be devised. In this book, the author deals with the two most common types of information: plain text, discussed in the first part, and semi-‐structured data, in particular XML documents, deeply discussed the second part. The detailed analysis of approximate matching, duplicate document detection, exact, approximate and semantic query answering, multi-‐version document management and personalized access techniques offered in this book will guide Information Technology professionals and users in effectively and efficiently managing information and knowledge, thus answering the increasingly complex
The ADT Proximity and Text Proximity Problems.

The EC Query Language Applied to Old Manuscripts.

The ADT Proximity and Text Proximity Problems.

Spaghettis An Array Based Algorithm for Similarity Queries in Metric Spaces.

Faster Approximate String Matching.
We present a new algorithm for on-line approximate string matching. The algorithm is based on the simulation of a non-deterministic finite automaton built from the pattern and using the text as input. This simulation uses bit operations on a RAM machine with word length w = \Omega\Gamma137 n) bits, where n is the text size. This is essentially similar to the model used in Wu and Manber&#039;s work, although we improve the search time by packing the automaton states differently. The running time achieved is O(n) for small patterns (i.e. whenever mk = O(log n)),  where m is the pattern length and k ! m the number of allowed errors. This is in contrast with the result of Wu and Manber, which is O(kn) for m = O(log n). Longer patterns can be processed by partitioning the automaton into many machine words, at O(mk=w n) search cost. We allow generalizations in the pattern, such as classes of characters, gaps and others, at essentially the same search cost. We then explore other novel techniques t...
Very Fast and Simple Approximate String Matching.
Abstract We improve the fastest known algorithm for approximate string matching. This algorithm can only be used for low error levels. By using a new algorithm to verify potential matches and a new optimization technique for biased texts (such as English), the algorithm becomes the fastest one for medium error levels too. This includes most of the interesting cases in this area.
Bounding the Expected Length of Longest Common Subsequences and Forests.
. We present two techniques to find lower and upper bounds for the expected length of longest common subsequences and forests of two random sequences of the same length, over a fixed size, uniformly distributed alphabet. We emphasize the power of the methods used, which are Markov chains and Kolmogorov complexity. As a corollary, we obtain some new lower and upper bounds for the problems mentioned. 1 Introduction  The longest common subsequence (LCS) of two strings is one of the main problems in combinatorial pattern matching. The LCS problem is related to DNA or protein alignments, file comparison, speech recognition, etc. We say that x is a subsequence of u if we can obtain x by deleting zero or more characters of u.  The LCS of two strings u and v of length n is defined as the longest subsequence  x common to u and v. For example, the LCS of longest and large is lge. An open problem related to the LCS is its expected length for two random strings of length n over a uniformly distrib...
Similarity in Two%2DDimensional Strings.

Searching the World Wide Web Challenges and Partial Solutions.
In this article we analyze the problem of searching the WWW, giving some insight and models to understand its complexity. Then we survey the two main current techniques used to search the WWW. Finally, we present recent results that can help to partially solve the challenges posed. 1
Fast Two%2DDimensional Approximate Pattern Matching

Fringe Analysis of Synchronized Parallel Algorithms on 2%2D3 Trees.
. We are interested in the fringe analysis of synchronized parallel insertion algorithms on 2--3 trees, namely the algorithm of W. Paul, U. Vishkin and H. Wagener (PVW). This algorithm inserts k keys into a tree of size n with parallel time O(log n + log k).  Fringe analysis studies the distribution of the bottom subtrees and it is still an open problem for parallel algorithms on search trees. To tackle this problem we introduce a new kind of algorithms whose two extreme cases seems to upper and lower bounds the performance of the PVW algorithm. We extend the fringe analysis to parallel algorithms and we get a rich mathematical structure giving new interpretations even in the sequential case. The process of insertions is modeled by a Markov chain and the coefficients of the transition matrix are related with the expected local behavior of our algorithm. Finally, we show that this matrix has a power expansion over (n+1)  \Gamma1  where the coefficients are the binomial transform of the ...
A Model for Visualizing Large Answers in WWW Retrieval.

Fast Searching on Compressed Text Allowing Errors.
We present a fast compression and decompression scheme for natural language texts that allows efficient and flexible string matching by searching the compressed text directly. The compression scheme uses a word-based Huffman encoding and the coding alphabet is byte-oriented rather than bit-oriented. We compress typical English texts to about 30% of their original size, against 40% and 35% for Compress and Gzip, respectively. Compression times are close to the times of Compress and approximately half the times of Gzip, and decompression times are lower than those of Gzip and one third of those of Compress.  The searching algorithm allows a large number of variations of the exact and approximate compressed string matching problem, such as phrases, ranges, complements, wild cards and arbitrary regular expressions. Separators and stopwords can be discarded at search time without significantly increasing the cost. The algorithm is based on a word-oriented shift-or algorithm and a fast Boyer-Moore-type filter. It concomitantly uses the vocabulary of the text available as part of the Huffman coding data. When searching for simple patterns, our experiments show that running our algorithm on a compressed text is twice as fast as running Agrep on the uncompressed version of the same text. When searching complex or approximate patterns, our algorithm is up to 8 times faster than Agrep. We also mention the impact of our technique in inverted files pointing to documents or logical blocks as Glimpse.   
Fast Approximate String Matching in a Dictionary.
A successful technique to search large textual databases allowing errors relies on an online search in the vocabulary of the text. To reduce the time of that online search, we index the vocabulary as a metric space. We show that with reasonable space overhead we can improve by a factor of two over the fastest online algorithms, when the tolerated error level is low (which is reasonable in text searching). 1 Introduction  Approximate string matching is a recurrent problem in many branches of computer science, with applications to text searching, computational biology, pattern recognition, signal processing, etc. The problem can be stated as follows: given a long text of length n, and a (comparatively short) pattern of length m, retrieve all the segments (or &#034;occurrences&#034;) of the text whose edit distance to the pattern is at most  k. The edit distance ed() between two strings is defined as the minimum number of character insertions, deletions and replacements needed to make them equal. I...

Searching the Web Challenges and Partial Solutions %28Invited Paper%29.

A Model and a Visual Query Language for Structured Text.
We present a new model to query document databases by content and structure. The main merits of the model are: it allows rich structure in the documents; the query algebra is intuitive (moreover, complemented by a visual query language) and powerful; it is efficiently implementable; it can be built on top of a traditional indexing system or even with no index at all; it is strongly oriented to user-definable relevance ranking instead of boolean logic; and it allows flexible visualization of results in terms of structure, contents and highlighting of user-defined important parts in the query. 1. Introduction  In the past five years the amount of information electronically available has experimented an impressive growth. As more and more textual information becomes available, the need for better search engines gains importance. One of the recent trends is to take advantage of the structure of documents to formulate more precise queries. Structure allows to give some context to the words ...
Direct Pattern Matching on Compressed Text.
We present a fast compression and decompression technique for natural language texts. The novelty is that the exact search can be done on the compressed text directly, using any known sequential pattern matching algorithm. Approximate search can also be done efficiently without any decoding. The compression scheme uses a semi-static word-based modeling and a Huffman coding where the coding alphabet is byte-oriented rather than bit-oriented. We use the first bit of each byte to mark the beginning of a word, which allows the searching of the compressed pattern directly on the compressed text. We achieve about 33% compression ratio for typical English texts. When searching for simple patterns, our experiments show that running our algorithm on a compressed text is almost twice as fast as running agrep on the uncompressed version of the same text. When searching complex or approximate patterns, our algorithm is up to 8 times faster than agrep.
A Practical q %2DGram Index for Text Retrieval Allowing Errors.
We propose an indexing technique for approximate text searching, which is practical and powerful, and especially optimized for natural language text. Unlike other indices of this kind, it is able to retrieve any string that approximately matches the search pattern, not only words. Every text substring of a fixed length q is stored in the index, together with pointers to all the text positions where it appears. The search pattern is partitioned into pieces which are searched in the index, and all their occurrences in the text are verified for a complete match. To reduce space requirements, pointers to blocks instead of exact positions can be used, which increases querying costs. We design an algorithm to optimize the pattern partition into pieces so that the total number of verifications is minimized. This is especially well suited for natural language texts, and allows to know in advance the expected cost of the search and the expected relevance of the query to the user. We show experi...
Analysis of Linear Hashing Revisited.
. In this paper we characterize several expansion techniques used for linear hashing and we present how to analyze any linear hashing technique that expands based on local events or that mixes local events and global conditions. As an example we give a very simple randomized expansion technique, which is easy to analyze and implement. Furthermore, we obtain the analysis of the original hashing technique devised by Litwin, which was unsolved until now, comparing it to the later and more widely used version of Larson&#039;s. We also analyze one hybrid technique. Among other results, it is shown that the control function used by Litwin does not produce a good storage utilization, matching known experimental data.  CR Classification: F.2.2, E.5, E.2.  Key words: external hashing, linear hashing, analysis of algorithms, optimal bucketing.  1. Introduction  External hashing is a very efficient technique used to obtain a fast organization and retrieval of information in big size files whose conten...
Block Addressing Indices for Approximate Text Retrieval.
Although the issue of approximate text retrieval is gaining importance in the last years, it is currently addressed by only a few indexing schemes. To reduce space requirements, the indices may point to text blocks instead of exact word positions. This is called &#034;block addressing&#034;. The most notorious index of this kind is Glimpse. However, block addressing has not been well studied yet, especially regarding approximate searching. Our main contribution is an analytical study of the spacetime trade-offs related to the block size. We find that, under reasonable assumptions, it is possible to build an index which is simultaneously sublinear in space overhead and in query time. We validate the analysis with extensive experiments, obtaining typical performance figures. These results are valid not only for approximate searching queries but also for classical ones. Finally, we propose a new strategy for approximate searching on block addressing indices, which we experimentally find 4-5 times f...
A first step to formally evaluate collaborative work.
We present an initial attempt to formally evaluate performance measures related to CSCW applications. In particular, we study the relations between the quality of the output, the number of people and time spent on the overall task and the total work done. We introduce a novel application to illustrate our ideas: collaborative retrieval. We propose a specific heuristic to the case when many people search for the same information, thereby increasing the recall and precision of the answer. We apply our evaluation methodology to this case.  Keywords: CSCW, quantitative evaluation, collaborative retrieval.  Introduction  The introduction of Computer Supported Cooperative Work (CSCW) tools within an organization can have a variety of positive outcomes [1]. Generally speaking, those benefits can be classified into three broad categories. The first type of benefits of CSCW introduction refers to an improved quality of the end product. Better documents, designs or decisions may be the result of...
Multiple Approximate String Matching.
We present two new algorithms for on-line multiple approximate string matching. These are extensions of previous algorithms that search for a single pattern. The single-pattern version of the first one is based on the simulation with bits of a non-deterministic finite automaton built from the pattern and using the text as input. To search for multiple patterns, we superimpose their automata, using the result as a filter. The second algorithm partitions the pattern in sub-patterns that are searched with no errors, with a fast exact multipattern search algorithm. To handle multiple patterns, we search the sub-patterns of all of them together. The average running time achieved is in both cases O(n) for moderate error level, pattern length and number of patterns. They adapt (with higher costs) to the other cases. However, the algorithms differ in speed and thresholds of usefulness. We analyze theoretically when each algorithm should be used, and show experimentally that they are faster ...
Proximal Nodes A Model to Query Document Databases by Content and Structure.
  A model to query document databases by both their content and structure is presented. The goal is to obtain a query language which is expressive in practice while being efficiently implementable, features not present at the same time in previous work. The key ideas of the model are a set-oriented query language based on operations on nearby structure elements of one or more hierarchies, together with content and structural indexing and bottom-up evaluation. The model is evaluated regarding expressiveness and efficiency, showing that it provides a good trade-off between both goals. Finally, it is shown how to include in the model other media different from text.  
Preface to the Special Issue on the 1995 Latin American Theoretical Informatics Symposium.


A Faster Algorithm for Approximate String Matching.
. We present a new algorithm for on-line approximate string matching. The algorithm is based on the simulation of a non-deterministic finite automaton built from the pattern and using the text as input. This simulation uses bit operations on a RAM machine with word length  O(log n), being n the maximum size of the text. The running time achieved is O(n) for small patterns (i.e. of length m = O(  p  log n)),  independently of the maximum number of errors allowed, k. This algorithm is then used to design two general algorithms. One of them partitions the problem into subproblems, while the other partitions the automaton into sub-automata. These algorithms are combined to obtain a hybrid algorithm which on average is O(n) for moderate k=m ratios,  O(  p  mk= log n n) for medium ratios, and O((m \Gamma k)kn= log n) for large ratios. We show experimentally that this hybrid algorithm is faster than previous ones for moderate size of patterns and error ratios, which is the case in text search...
AccessNova broadband networks and multimedia services experiments.

A Unified View to String Matching Algorithms.
  We present a unified view to sequential algorithms for many  pattern matching problems, using a finite automaton built from the pattern  which uses the text as input. We show the limitations of deterministic  finite automata (DFA) and the advantages of using a bitwise  simulation of non-deterministic finite automata (NFA). This approach  gives very fast practical algorithms which have good complexity for small  patterns on a RAM machine with word length O(log n), where n is the  size of the text. For generalized string matching the time complexity is  O(mn= log n) which for small patterns is linear. For approximate string  matching we show that the two main known approaches to the problem  are variations of the NFA simulation. For this case we present a different  simulation technique which gives a running time of O(n) independently  of the maximum number of errors allowed, k, for small patterns. This  algorithm improves the best bit-wise or comparison based algorithms of  running ti...
Fast and Practical Approximate String Matching.
We present new algorithms for approximate string matching based in simple, but efficient, ideas. First, we present an algorithm for string matching with mismatches based in arithmetical operations that runs in linear worst case time for most practical cases. This is a new approach to string searching. Second, we present an algorithm for string matching with errors based on partitioning the pattern that requires linear expected time for typical inputs. 1 Introduction  Approximate string matching is one of the main problems in combinatorial pattern matching. Recently, several new approaches emphasizing the expected search time and practicality have appeared [3, 4, 27, 32, 31, 17], in contrast to older results, most of them are only of theoretical interest. Here, we continue this trend, by presenting two new simple and efficient algorithms for approximate string matching. First, we present an algorithm for string matching with k mismatches. This problem consists of finding all instances o...
A Framework to Animate String Algorithms.
We present an algorithm animation system, Xaa, which is tailored for string algorithms, and, in general, to algorithms that have as input one or two dimensional sequences of symbols. This system provides data generation tools and statistics of the algorithm&#039;s behavior. 1 Introduction  Visualization of a dynamic process facilitates its understanding. There are several general purpose algorithm animation systems [Bro88, Sta90, Bro91], the best known of which is BALSA [Bro88]. Although BALSA is incredibly powerful, it is not trivial to define a new visualization, and the learning effort for this system is high. One solution is to trade functionality by automatically generating animation code, this approach was used in VCC [BYJQ92]. Another solution, which is taken in this paper, it is to tailor the animation primitives to a specific class of algorithms. This solution simplifies the animation of an algorithm, and it includes functionality common to the class of algorithms selected. Here we...
Hierarchies of Indices for Text Searching.
We present an efficient implementation of a recently known index for text databases, when the database is stored on secondary storage devices such as magnetic or optical disks. The implementation is built on top of a new and simple index for texts called pat array (or suffix array). Considering that text searching in a large database spends most of the time accessing external storage devices, we propose additional index structures and searching algorithms for pat arrays that reduce the number of disk accesses. We present two index structures: a two-level hierarchy model that uses main memory and one level of external storage (magnetic or optical devices) and a three-level hierarchy model that uses main memory and two levels of external storage (magnetic and optical devices). Performance improvement is achieved in both models by storing most of higher index levels in faster memories, thus reducing accesses in the slowest devices in the hierarchy. Analytical and experimental results are ...
Fast Text Searching for Regular Expressions or Automaton Searching on Tries.
  We present algorithms for efficient searching of regular expressions on preprocessed text, using a Patricia tree as a logical model for the index. We obtain searching algorithms that run in logarithmic expected time in the size of the text for a wide subclass of regular expressions, and in sublinear expected time for any regular expression. This is the first such algorithm to be found with this complexity.
Integrating Contents and Structure in Text Retrieval.

Bounded Disorder The Effect of the Index.
In this paper we complete the analysis done by Ramakrishna and Mukhopadhyay for a data node in the Bounded Disorder (BD) file organization of Litwin and Lomet, by introducing the B-tree index into the model. Also, we extend the analysis to the case of BD files with two partial expansions as proposed by Lomet. Our main contribution is a detailed analysis of search and insertion costs, and its comparison with B  +  -trees. 1 Introduction  Nowadays there are two main file organizations: hashing and tree indexing. New hashing techniques achieve single access retrieval, but are very inefficient for range search or key sequential access. On the other hand tree indices preserve the key order with a higher search cost. Litwin and Lomet [9] proposed the Bounded Disorder (BD) file organization to combine the advantages of both methods. This paper complements the analysis presented by Ramakrishna and Mukhopadhyay [14] concerning the performance of BD files, by including the index in their model. ...
LATIN %2795 Theoretical Informatics

Optimized Binary Search and Text Retrieval.
. We present an algorithm that minimizes the expected cost of indirect binary search for data with non-constant access costs, such as disk data. Indirect binary search means that sorted access to the data is obtained through an array of pointers to the raw data. One immediate application of this algorithm is to improve the retrieval performance of disk databases that are indexed using the suffix array model (also called  pat array). We consider the cost model of magnetic and optical disks and the anticipated knowledge of the expected size of the subproblem produced by reading each disk track. This information is used to devise a modified binary searching algorithm to decrease overall retrieval costs. Both an optimal and a practical algorithm are presented, together with analytical and experimental results. For 100 megabytes of text the practical algorithm costs 60% of the standard binary search cost for the magnetic disk and 65% for the optical disk.  key-words: Optimized binary search...
A Language for Queries on Structure and Contents of Textual.

Fringe Analysis Revisited.
Fringe analysis is a technique used to study the average behavior of search trees. In this paper we survey the main results regarding this technique, and we improve a previous asymptotic theorem. At the same time we present new developments and applications of the theory which allow improvements in several bounds on the behavior of search trees. Our examples cover binary search trees, AVL trees, 2-3 trees, and B-trees. Categories and Subject Descriptors: F.2.2 [Analysis of Algorithms and Problem Complexity ]: Nonnumerical Algorithms and Problems -- computations on discrete structures; sorting and searching; E.1 [Data Structures]; trees. Contents  1 Introduction 2 2 The Theory of Fringe Analysis 4 3 Weakly Closed Collections 9 4 Including the Level Information 11 5 Fringe Analysis, Markov Chains, and Urn Processes 13    This work was partially funded by Research Grant FONDECYT 93-0765. e-mail: rbaeza@dcc.uchile.cl  1 Introduction  Search trees are one of the most used data structures t...
Computing in Chile The Jaguar of the Pacific Rim%3F

Parallel Searching in the Plane.
We consider the problem of k robots searching on an integer lattice on the plane. We give a  strategy for nding a target at an unknown distance away using k = 2  j  searchers, where j  2,  at a competitive ratio of n=2  j 1  + 1. We give a lower bound for general k of 2n=k. We also give  matching upper and lower bounds for the special case k = 2.  1 
Higher%2DOrder Analysis of 2%2D3 Trees.
We present a fourth-order fringe analysis for the expected behavior of 2-3 trees, which includes 97% of the elements in the tree. It is accomplished by exploiting the structure of the transition matrix. Our results improve a number of bounds, in particular the bounds on the expected number of nodes and the expected space utilization. We also study 2-3 trees built by using overflow techniques. 1 Introduction  Fringe analysis was formally introduced by Yao in 1974 [Yao74, Yao78] as a method to analyze search trees that considers only the bottom part or fringe of the tree. From the behavior of the subtrees in the fringe, it is possible to obtain bounds on most complexity measures for the complete tree, as well as some exact results. Classical fringe analysis considers only insertions. The model assumes that the n! possible permutations of the n keys used as input are equally likely. A search tree built under this model is called a random tree. This is equivalent to saying that the n-th in...
Teaching algorithms.
We describe Fuse-N, a system for distributed, Web-based teaching of algorithmic concepts through experimentation, implementation, and automated test and verification. Fuse-N is accessible to, and usable by, anyone with a Java-enabled Web browser. The system was designed to 1) minimize the overhead required for students to engage in the essence of the learning experience; 2) allow students to experiment with, generate, and evaluate algorithms and their implementations; and 3) facilitate greater, more effective interaction among students and between students and teaching staff. The system represents algorithmic concepts as dynamic modules in Java. Students map inputs to outputs either via system-supplied &#034;reference&#034; implementations; manually, with corrective feedback; or (most commonly) by writing one or more alternative implementations for the concept. The output of the student&#039;s implementation is programmatically and visually compared to that of the reference implementation. Modules ca...
Proximity Matching Using Fixed%2DQueries Trees.
. We present a new data structure, called the fixed-queries tree, for the problem of finding all elements of a fixed set that are close, under some distance function, to a query element. Fixedqueries trees can be used for any distance function, not necessarily even a metric, as long as it satisfies the triangle inequality. We give an analysis of several performance parameters of fixed-queries trees and experimental results that support the analysis. Fixed-queries trees are particularly efficient for applications in which comparing two elements is expensive. 1 Introduction  Search structures such as hashing and trees are at the basis of many efficient computer science applications. But they usually support only exact queries. Finding things approximately, that is, allowing some errors in the query specifications, is much harder. The first question that a prominent biologist once asked one of the authors when finding that he is a computer scientist is whether it is possible to adapt bina...
Analysis of Bounded Disorder.
This memory must be dedicated to serving the B-tree. It saves accesses at whatever the rate is that the disk can sustain. We have set things up so that it takes one disk access to get to a record. Thus, the record access rate is the disk access rate. It is
Hierarchies of Indices for Text Searching.
We present an efficient implementation of a recently known index for text databases, when the database is stored on secondary storage devices such as magnetic or optical disks. The implementation is built on top of a new and simple index for texts called pat array (or suffix array). Considering that text searching in a large database spends most of the time accessing external storage devices, we propose additional index structures and searching algorithms for pat arrays that reduce the number of disk accesses. We present two index structures: a two-level hierarchy model that uses main memory and one level of external storage (magnetic or optical devices) and a three-level hierarchy model that uses main memory and two levels of external storage (magnetic and optical devices). Performance improvement is achieved in both models by storing most of higher index levels in faster memories, thus reducing accesses in the slowest devices in the hierarchy. Analytical and experimental results are ...
On Boyer%2DMoore Automata.
The notion of Boyer-Moore automaton was introduced by Knuth, Morris and Pratt in their historical paper on fast pattern matching. It leads to an algorithm that requires more preprocessing but is more efficient than the original Boyer-Moore&#039;s algorithm. We formalize the notion of Boyer-Moore automaton, and we give an efficient building algorithm. Also, bounds on the number of states are presented, and the concept of potential of a transition is introduced to improve the worst and average case behavior of these machines. We show that looking at the rightmost unknown character, as suggested by Knuth et al., is not necessarily optimal.  Keywords: string searching, pattern matching, finite automaton, average case analysis.  1 Introduction  String searching is a very important component of many problems, including text editing, data retrieval and letter manipulation. Formally, the string searching or string matching problem consists in finding all occurrences (or the first occurrence) of a p...
String Searching Algorithms.
The problem of approximate string searching comprises two classes of problems: string searching with k mismatches and string searching with k differences. In this paper we present a short survey and experimental results for well known sequential approximate string searching algorithms. We consider algorithms based on different approaches including dynamic programming, deterministic finite automata, filtering, counting and bit parallelism. We compare these algorithms in terms of running time against pattern length and for several values of k for four different kinds of text: binary alphabet, alphabet of size 8, English alphabet and DNA alphabet. Finally, we compare the experimental results of the algorithms with their theoretical complexities.
Fast String Matching with Mismatches
We describe and analyze three simple and fast algorithms on the average for solving the problem of string matching with a bounded number of mismatches. These are the naive algorithm, an algorithm based on the Boyer-Moore approach, and ad-hoc deterministic finite automata searching. We include simulation results that compare these algorithms to previous works. 1 Introduction  The problem of string matching with k mismatches consists of finding all occurrences of a pattern of length m in a text of length n such that in at most k positions the text and the pattern have different symbols. In the following, we assume that 0 ! k ! m and m  n. The case of k = 0 is the well known exact string matching problem, and if k = m the solution is trivial. Landau and Vishkin [LV86] gave the first efficient algorithm to solve this particular problem. Their algorithm uses O(kn + km log m)) time and O(k(n + m)) space. While it is fast, the space required is unacceptable for most practical purposes. Galil ...
Visual and Collaborative Tools for Software Engineering Education.

On Efficient Entreeings.

Searching in the Plane
In this paper we initiate a new area of study dealing with the best way to search a possibly unbounded region for an object. The model for our search algorithms is that we must pay costs proportional to the distance of the next probe position relative to our current position. This model is meant to give a realistic cost measure for a robot moving in the plane. We also examine the effect of decreasing the amount of a priori information given to search problems. Problems of this type are very simple analogues of non-trivial problems on searching an unbounded region, processing digitized images, and robot navigation. We show that for some simple search problems, the relative information of knowing the general direction of the goal is much higher than knowing the distance to the goal.
Fast Two%2DDimensional Pattern Matching.

Information Retrieval Data Structures %26 Algorithms
We survey two indices for text, with emphasis on Pat arrays (also  called suffix arrays). A Pat array is an index based on a new model  of text which does not use the concept of word and does not need to  know the structure of the text.  to appear in Information Retrieval: Data Structures and Algorithms,  R.A. Baeza-Yates and W. Frakes, eds., Prentice-Hall.  1  1 Introduction  Text searching methods may be classified as lexicographical indices (indices that are sorted), clustering techniques, and indices based on hashing (for example, signature files [FC87]). In this report we discuss lexicographical indices, in particular, two main data structures: inverted files and Pat trees. Our aim is to build an index for the text of size similar to or smaller than the text.  Briefly, the traditional model of text used in information retrieval is that of a set of documents. Each document is assigned a list of keywords (attributes), with optional relevance weights associated to each keyword. This ...
Fast and Practical Approximate String Matching.
We present new algorithms for approximate string matching based in simple, but efficient, ideas. First, we present an algorithm for string matching with mismatches based in arithmetical operations that runs in linear worst case time for most practical cases. This is a new approach to string searching. Second, we present an algorithm for string matching with errors based on partitioning the pattern that requires linear expected time for typical inputs. 1 Introduction  Approximate string matching is one of the main problems in combinatorial pattern matching. Recently, several new approaches emphasizing the expected search time and practicality have appeared [3, 4, 27, 32, 31, 17], in contrast to older results, most of them are only of theoretical interest. Here, we continue this trend, by presenting two new simple and efficient algorithms for approximate string matching. First, we present an algorithm for string matching with k mismatches. This problem consists of finding all instances o...
Text%2DRetrieval Theory and Practice.
We present the state of the art of the main component of text retrieval systems: the searching engine. We outline the main lines of research and issues involved. We survey recently published results for text searching and we explore the gap between theoretical vs. practical algorithms. The main observation is that simpler ideas are better in practice.  1597 Shaks. Lover&#039;s Compl. 2 From off a hill whose concaue wombe reworded A plaintfull story from a sistring vale.  OED2, reword, sistering  1 1 Introduction  Full text retrieval systems are becoming a popular way of providing support for on-line text. Their main advantage is that they avoid the complicated and expensive process of semantic indexing. From the end-user point of view, full text searching of on-line documents is appealing because a valid query is just any word or sentence of the document. However, when the desired answer cannot be obtained with a simple query, the user must perform his/her own semantic processing to guess w...
Innovation as a Critical Success Factor for the Development of an Information Technology Industry in Chile.
Chile presents an interesting case of development of information processing and technology. Its open-market policies, good education level and early adoption of computer technology have allowed its exports to become competitive on an international basis. This has been a pioneering approach in Latin-America. The Chilean software industry has had some initial success and it is attempting to grow to become an international player. It is argued that several factors must be present to reach this objective and that these elements must have innovation as a common floor. Government, Industry and universities should work in a coordinated fashion to establish these elements. Tasks for each of these actors are discussed. Finally, an assessment of the feasibility of these ideas in Chile and other countries of Latin-America is made.  Note: This paper was presented in IFIP Congress 1992 in Madrid, Spain. 1 Introduction  Chile, with 13 million inhabitants shares many of the cultural assets with other...
Introduction to Data Structures and Algorithms Related to Information Retrieval.

String Searching Algorithms.
The problem of approximate string searching comprises two classes of problems: string searching with k mismatches and string searching with k differences. In this paper we present a short survey and experimental results for well known sequential approximate string searching algorithms. We consider algorithms based on different approaches including dynamic programming, deterministic finite automata, filtering, counting and bit parallelism. We compare these algorithms in terms of running time against pattern length and for several values of k for four different kinds of text: binary alphabet, alphabet of size 8, English alphabet and DNA alphabet. Finally, we compare the experimental results of the algorithms with their theoretical complexities.
Inverted Files.
Research into inverted file compression has focused on compression ratio---how small the indexes can be. Compression ratio is important for fast interactive searching. It is taken as read, the smaller the index, the faster the search.
New Indices for Text Pat Trees and Pat Arrays.

Unbalanced Multiway Trees Improved by Partial Expansions.

Improved Bounds for the Expected Behaviour of AVL Trees.
In this paper we improve previous bounds on expected measures of AVL trees by using fringe analysis. A new way of handling larger tree collections that are not closed is presented. An inherent difficulty posed by the transformations necessary to keep the AVL tree balanced makes its analysis difficult when using fringe analysis methods. We derive a technique to cope with this difficulty obtaining the exact solution for fringe parameters even when unknown probabilities are involved. We show that the probability of a rotation in an insertion is between 0.37 and 0.73 (and seems to be less than 0.56), that the fraction of balanced nodes is between 0.56 and 0.78, and that the expected number of comparisons in a search seems to be at most 12% more than in the complete balanced tree.  CR Categories: E.1, F.2.2, G.2.1. 1 Introduction  Balanced tree structures are efficient ways of storing information. They provide an excellent solution for the dictionary data structure problem. For N elements t...
A New Approach to Text Searching.
We introduce a family of simple and fast algorithms for solving the classical string matching problem, string matching with classes of symbols, don&#039;t care symbols and complement symbols, and multiple patterns. In addition we solve the same problems allowing up to k mismatches. Among the features of these algorithms are that they don&#039;t need to buffer the input, they are real time algorithms (for constant size patterns), and they are suitable to be implemented in hardware. 1 Introduction  String searching is a very important component of many problems, including text editing, bibliographic retrieval, and symbol manipulation. Recent surveys of string searching can be found in [17, 4]. The string matching problem consists of finding all occurrences of a pattern of length  m in a text of length n. We generalize the problem allowing &#034;don&#039;t care&#034; symbols, the complement of a symbol, and any finite class of symbols. We solve this problem for one or more patterns, with or without mismatches. Fo...
On the Average Size of the Intersection of Binary Trees.
In this paper we study a balanced probability model defined over simple families of trees, which from the point of doing statistics on trees, behave in quite a different way from the uniform distribution.  Using the new model, the analysis itself is more complex, but feasible. We illustrate our point by working out some particular simple cases of study : the computation of occupancy (a measure of the degree of balancing in trees), and the average size of the intersection of two m-ary trees. The development of the last analysis involves the use of sophisticated tools, such as Riemman&#039;s method to solve partial differential equations. These average complexities are then compared with the ones obtained if the uniform model is assumed. 1 Introduction  The uniform probability model for the input is a current assumption in many average-case analysis, due to several reasons. Among others there are many applications where this model accurately enough approximates the actual probability distribu...
Average Running Time of the Boyer%2DMoore%2DHorspool Algorithm.

An Algorithm for String Matching with a Sequence of don%27t Cares.

Height Balance Distribution of Search Trees.

Searching Subsequences.
The thesis deals with the subsequence matching problem. We describe two approaches: preprocessing the pattern and preprocessing the text. Preprocessing the pattern involves building the searching automaton that searches for all non-overlapping occurrences of the given pattern. We consider the case of multiple patterns and present an algorithm for building the automaton that searches for all non-overlapping occurrences of each pattern from the set of patterns. Preprocessing the text consists of building the automaton which accepts all subsequences of the given text. Such automaton is called Directed Acyclic Subsequence Graph (DASG). We present an incremental algorithm for building the DASG and use encoding to reduce the number of its transitions. We show how to modify the DASG if the text has been changed. Further, we consider the case of multiple texts and present two algorithms for building the DASG for the set of texts. The subsequence matching problem for a finite regular language is also mentioned. We describe a modification of the DASG for episode matching. We also show a correspondence between the searching automaton and the DASG.
An Adaptive Overflow Technique for B%2Dtrees.
We present a new overflow technique for B-trees. The technique is a hybrid of partial expansions and unbalanced splits. This technique is asymmetric and adaptive. Considering a growing file (only insertions), the storage utilization is 77% for random keys, 70% for sorted keys, and over 75% for non-uniform distributed keys. Similar results are achieved when we have deletions mixed with insertions. One of the main properties of this technique is that the storage utilization is very stable with respect to changes of the data distribution. This technique may be used for other bucket-based file structures, like extendible hashing or bounded disorder files. 1 Introduction  The B  +  -tree is one of the most widely used file organizations. In a B  +  -tree all the information is stored at the lowest level (buckets), and the upper levels are a B-tree index. File growth is handled by bucket splitting, that is, when a bucket overflows, a new bucket is allocated and half of the records from the o...
Average Case Analysis of Algorithms using Matrix Recurrences.

Analysis of Boyer%2DMoore%2DType String Searching Algorithms.

Expected Behaviour Analysis of AVL Trees.

Fast Algorithms for Two Dimensional and Multiple Pattern Matching %28Preliminary Version%29.

An Analysis of the Karp%2DRabin String Matching Algorithm.

A dynamic storage allocation algorithm suitable for file structures.

Efficient Text Searching of Regular Expressions %28Extended Abstract%29.

A New Approach to Text Searching.
We introduce a family of simple and fast algorithms for solving the classical string matching problem, string matching with classes of symbols, don&#039;t care symbols and complement symbols, and multiple patterns. In addition we solve the same problems allowing up to k mismatches. Among the features of these algorithms are that they don&#039;t need to buffer the input, they are real time algorithms (for constant size patterns), and they are suitable to be implemented in hardware. 1 Introduction  String searching is a very important component of many problems, including text editing, bibliographic retrieval, and symbol manipulation. Recent surveys of string searching can be found in [17, 4]. The string matching problem consists of finding all occurrences of a pattern of length  m in a text of length n. We generalize the problem allowing &#034;don&#039;t care&#034; symbols, the complement of a symbol, and any finite class of symbols. We solve this problem for one or more patterns, with or without mismatches. Fo...
The Subsequence Graph of a Text.

Efficient Text Searching of Regular Expressions.

String Searching Algorithms Revisited.

Modeling Splits in File Structures.

The Expected Behaviour of B %2DTrees.

A Trivial Algorithm Whose Analysis is Not A Continuation.

Performance of B %2DTrees with Partial Expansions.

Algorithms for String Searching A Survey.

A New Approach to Text Searching %28correction%29.

Improved String Searching.
this report emphasized the fact that Dilemma is a prototype and not a running commercial product. The prototype has been effective enough (with respect to speed) for evaluation. Some algorithms used in Dilemma are, however, not optimal. There are at least two implementational details that can be improved. First, the string searching algorithm currently implemented in Dilemma is naive and inefficient. There exist many well-documented fast string searching algorithms that would improve the string searching process (Boyer and Moore, 1977). Secondly, the management of the words that are considered during the translation process (class WordTable) can be improved further (for example, better implementation of hash tables and improved algorithms for key generation). Functionality One extension of Dilemma&#039;s functionality is to present translations of text fragments instead of words. Translating words is a special case (the lowest hierarchical level). The method for presenting text fragments at higher hierarchical levels should not be a difficult extension. Probably the method defined in section 4.5 will work satisfactorily at any hierarchical level, but we have not verified this assumption. Another extension in the interface is to let the user navigate among the different hierarchical levels in the text. Dilemma supports several hierarchical levels, but the user can only switch between two levels (for example between phrases and paragraphs). The problem of navigating in large volumes of information is out of the scope of this report and is therefore deferred to future work.  Nordström &amp; Pettersson Preparatory Work Dilemma must have previously translated text, preferably containing similar i nformation as the one being translated, in order to be useful for a translator. Essenti...
Searching with Uncertainty %28Extended Abstract%29.

Some Average Measures in m%2Dary Search Trees.

